class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(auto& e : nums)
        {
            if(e <= 0)
                e = n + 1;
        }
        for(int i = 0; i < n; ++i)
        {
            int val = abs(nums[i]);
            if(val <= n)
                nums[val - 1] =  -abs(nums[val - 1]);
        }

        for(int i = 0; i < n; ++i)
        {
            if(nums[i] > 0)
                return i + 1;
        }
        return n + 1;
    }
};

/*class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int n = nums.size();
        int maxNum = -INT_MAX;
        for(int i = 0; i < n; ++i)
        {
            maxNum = max(nums[i], maxNum);
        }
        for(int i = 1; i < maxNum; ++i)
        {
            if(!s.count(i))
                return i;
        }
        return maxNum < 0 ? 1 : maxNum + 1;
    }
};*/